#!/usr/bin/python3.5

# -*- coding: utf-8 -*-

def _merge(arr,l,r,mid):
    a = []
    lm= l
    rm=mid
    for i in range(l,r+1):
        if lm<mid and rm<r:
            if arr[lm] < arr[rm]:
                a.append(arr[lm])
                lm+=1
            else:
                a.append(arr[rm])
                rm+=1
    if lm>=mid:
        a.extend(arr[rm:r])
    if rm>=r:
        a.extend(arr[lm:mid])
    arr[l:r]=a
    return arr

def mergeSort(arr,l,r):

    if r-l<=1:
        return
    mid = int((r+l)/2)
    mergeSort(arr,l,mid)
    mergeSort(arr,mid,r)
    _merge(arr,l,r, mid)

    return arr


if __name__ =="__main__":

    a = [2, 8, 4, 5, 9, 4, 42, 0, 3, 6, 8]
    print(mergeSort(a,0,11))

